import java.util.PriorityQueue;

public class Solution {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    /**
     * 两数相加
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode();
        ListNode cur1 = l1, cur2 = l2, cur = newHead;
        int carry = 0, count = 0;
        while(cur1 != null && cur2 != null) {
            count = (cur1.val + cur2.val + carry) % 10;
            carry = (cur1.val + cur2.val + carry) / 10;
            ListNode node = new ListNode(count);
            cur.next = node;
            cur = cur.next;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        while(cur1 != null) {
            count = (cur1.val + carry) % 10;
            carry = (cur1.val + carry) / 10;
            ListNode node = new ListNode(count);
            cur.next = node;
            cur = cur.next;
            cur1 = cur1.next;
        }
        while(cur2 != null) {
            count = (cur2.val + carry) % 10;
            carry = (cur2.val + carry) / 10;
            ListNode node = new ListNode(count);
            cur.next = node;
            cur = cur.next;
            cur2 = cur2.next;
        }
        if (carry > 0) {
            ListNode node = new ListNode(carry);
            cur.next = node;
        }
        return newHead.next;
    }

    /**
     * 两两交换链表中的节点
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode cur = head, nextNode = head.next, prev = newHead;
        while(cur != null && nextNode != null) {
            // 交换
            ListNode next = nextNode.next;
            prev.next = nextNode;
            nextNode.next = cur;
            cur.next = next;
            // 移动
            prev = cur;
            if (cur != null) {
                cur = next;
            }
            if (next != null) {
                nextNode = next.next;
            }

        }
        return newHead.next;
    }

    /**
     * 重排链表
     * @param head
     */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        // 找到中间节点
        ListNode slow = head, fast = head.next;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 翻转链表
        ListNode head2 = reverse(slow.next);
        slow.next = null;
        // 合并两链表
        ListNode cur1 = head, next1 = head.next, cur2 = head2, next2 = head2.next;
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        while(cur1 != null && cur2 != null) {
            cur.next = cur1;
            cur1.next = cur2;
            cur = cur2;
            cur1 = next1;
            cur2 = next2;
            if (next1 != null) {
                next1 = next1.next;
            }
            if (next2 != null) {
                next2 = next2.next;
            }
        }
        if (cur1 != null) {
            cur.next = cur1;
        }
        if (cur2 != null) {
            cur.next = cur2;
        }
        head = newHead.next;
    }

    // 翻转链表(使用头插法进行翻转)
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newNode = new ListNode();
        ListNode cur = head, next = head.next;
        while(cur != null) {
            cur.next = newNode.next;
            newNode.next = cur;
            cur = next;
            if (next != null) {
                next = next.next;
            }
        }
        return newNode.next;
    }

    /**
     * 合并 k 个升序链表
     * 归并
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return mergeKLists(lists, 0, lists.length - 1);
    }
    public ListNode mergeKLists(ListNode[] lists, int left, int right) {
        // 递归出口
        if (left >= right) {
            return lists[left];
        }
        if (left + 1 == right) {
            return mergeLists(lists[left], lists[right]);
        }
        // 继续递归
        int mid = (left + right) / 2;
        ListNode leftHead = mergeKLists(lists, left, mid);
        ListNode rightHead = mergeKLists(lists, mid + 1, right);
        // 合并
        return mergeLists(leftHead, rightHead);
    }

    // 合并两个有序链表
    public ListNode mergeLists(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        ListNode cur1 = head1, next1 = head1.next;
        ListNode cur2 = head2, next2 = head2.next;
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                cur.next = cur1;
                cur = cur1;
                cur1 = next1;
                if (next1 != null) {
                    next1 = next1.next;
                }
            } else {
                cur.next = cur2;
                cur = cur2;
                cur2 = next2;
                if (next2 != null) {
                    next2 = next2.next;
                }
            }
        }
        if (cur1 != null) {
            cur.next = cur1;
        }
        if (cur2 != null) {
            cur.next = cur2;
        }
        return newHead.next;
    }

    /**
     * 合并 K 个升序链表
     * 利用堆进行排序
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        // 建立小根堆
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        // 将所有头节点加入小根堆中
        for (int i = 0; i < lists.length; i++) {
            if (null != lists[i]) {
                priorityQueue.add(lists[i]);
            }
        }
        // 调整堆
        ListNode head = new ListNode();
        ListNode cur = head;
        while(!priorityQueue.isEmpty()) {
            ListNode minNode = priorityQueue.poll();
            cur.next = minNode;
            cur = cur.next;
            if (minNode.next != null) {
                priorityQueue.add(minNode.next);
            }
        }
        return head.next;
    }

    /**
     * k 个一组翻转链表
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        int count = 0;
        ListNode cur = head;
        // 计算节点个数
        while(cur != null) {
            cur = cur.next;
            count++;
        }
        // 计算翻转次数
        count /= k;
        // 翻转
        cur = head;
        ListNode newHead = new ListNode();
        ListNode prev = newHead;
        for(int i = 0; i < count; i++) {
            // 记录翻转之后的最后一个节点
            ListNode tmp = cur;
            for(int j = 0; j < k; j++) {
                // 头插
                ListNode next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
                cur = next;
            }
            prev = tmp;
        }
        // 连接剩下的节点
        prev.next = cur;
        return newHead.next;
    }
}
